package 剑指offer.demo1;//https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?

/**
 * 思路：经过旋转的，可以分成前后两部分，二分查找定义中间值mid，left<=mid：左面递增，目标最小值min在右面；mid<left：最小值在左面
 * 1、垃圾牛客不要这样写"mid = left + (right - left) >> 1;"不通过
 */
public class 旋转数组的最小数字 {
    public int minNumberInRotateArray(int [] array) {
        //合法性判定
        if (array == null || array.length == 0){
            return 0;
        }
        //确定左中右的值索引下标
        int left = 0;
        int right = array.length - 1;
        int mid = left + (right - left) >> 1;
        //最小值索引下标
        int min = 0;
        //如果left一开始就小于right说明整个数组递增最左面就是最小值
        while (array[left] >= array[right]){
            //如果left与right相邻的话，此时右边的值就是最小值
            if (right - left == 1){
                min = right;
                break;
            }
            //如果left = right = mid 时不知道最小值在哪面，遍历查找即可
            if (array[left] == array[mid] && array[mid] == array[right]){
                for (int i = left + 1; i < right; i++) {
                    if (array[i] < array[min]){
                        min = i;
                    }
                }
            }
            //left<=mid左面还在非递减过程中最小值在右面
            if (array[left] <= array[mid]){
                left = mid;
            }else {
                //否则在左面
                right = mid;
            }
            //更新mid值
            mid = left + (right - left) / 2;
        }
        return array[min];
    }
}
